package com.hanxiaozhang.no10leetcode.tree;

import com.hanxiaozhang.no1javabase.no2extend.A;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一棵二叉树，按层以从左至右的顺序返回二叉树的值〉
 * <p>
 * 思路：
 * 1.使用一个帮助队列，首先将根节点添加进队列。
 * 2.判断帮助队列是否为空，不为空时，保存当前元素的值。然后判断左孩子结点是否为空，不为空时，添加至帮助队列。
 * 最后判断右孩子结点是否为空，不为空时，添加至帮助队列。
 * 3.循环步骤2。
 *
 * @author hanxinghua
 * @create 2024/4/8
 * @since 1.0.0
 */
public class No102BinaryTreeLevelOrderTraversal {


    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(5);
        tree1.left = new TreeNode(1);
        tree1.right = new TreeNode(4);
        tree1.right.left = new TreeNode(3);
        tree1.right.right = new TreeNode(6);

        System.out.println(method1(tree1));

    }

    /**
     * 方法1
     * 思路：
     * 知识点1：使用队列特性，先进先出。
     * 知识点2：添加节点顺序：
     * - 1. 将头节点添加进队列。
     * - 2. 判断队列是否为空，弹出队列元素（即弹出头结点），再将头结点左孩子节点加进队列，再将头结点右孩子节点加入进队。
     * - 3. 判断队列是否为空，弹出队列元素（即弹出头结点的左孩子结点），再将头结点的左孩子的左孩子结点加进队列，再将头结点的左孩子的右孩子结点加进队列
     * - 4. 以此类推
     *
     * @param root
     * @return
     */
    private static List<Integer> method1(TreeNode root) {

        List<Integer> results = new ArrayList();
        if (root == null) {
            return results;
        }
        LinkedList<TreeNode> helpQueue = new LinkedList<>();
        helpQueue.add(root);

        while (!helpQueue.isEmpty()) {

            TreeNode node = helpQueue.poll();
            results.add(node.val);

            if (node.left != null) {
                helpQueue.add(node.left);
            }

            if (node.right != null) {
                helpQueue.add(node.right);
            }
        }

        return results;

    }


}
